package algorithm.t202111;

import com.sun.jmx.remote.internal.ArrayQueue;
import com.sun.scenario.effect.impl.sw.java.JSWBlend_OVERLAYPeer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/3 9:57
 * @description :6道
 * 都会随青春，一笑了之。
 * persevere to last
 * 2021.11.03
 */
public class t20211103 {

    //407.接雨水
    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0) {
            return 0;
        }
        int res = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[2] - b[2]);

        int rows = heightMap.length, columns = heightMap[0].length;
        boolean[][] visit = new boolean[rows][columns];


        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (i == 0 || i == rows - 1 || j == 0 || j == columns - 1) {
                    queue.offer(new int[]{i, j, heightMap[i][j]});
                    visit[i][j] = true;
                }
            }
        }

        //方向数组
        int[] dir = {-1, 0, 1, 0, -1};

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();

            int x = arr[0], y = arr[1], h = arr[2];

            //四个方向进行查找
            for (int i = 0; i < 4; i++) {
                int nx = x + dir[i], ny = y + dir[i + 1];


                if (nx >= 0 && nx < rows && ny >= 0 && ny < columns && !visit[nx][ny]) {
                    if (h > heightMap[nx][ny]) {
                        //此点可以接雨水
                        res += arr[2] - heightMap[nx][ny];
                    }

                    queue.add(new int[]{nx, ny, Math.max(h, heightMap[nx][ny])});
                    visit[nx][ny] = true;

                }

            }

        }

        return res;
    }

    //17.电话号码的字母组合
    public List<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        HashMap<Integer, List<Character>> map = new HashMap<>();
        map.put(1, new ArrayList<>());

        int count = 97;
        for (int i = 2; i <= 9; i++) {
            ArrayList<Character> temp = new ArrayList<>();
            for (int j = 0; j < 3; j++) {
                temp.add((char) count++);
            }
            if (i == 7 || i == 9) {
                temp.add((char) count++);
            }
            map.put(i, new ArrayList<>(temp));
        }

        combination(digits, map, res);


        return res;

    }

    private void combination(String digits, HashMap<Integer, List<Character>> map, ArrayList<String> res) {
        int len = digits.length();
        ArrayList<List<Character>> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            List<Character> characters = map.get(Integer.valueOf(digits.charAt(i) + ""));
            list.add(characters);
        }

        StringBuilder builder = new StringBuilder();
        for (List<Character> element : list) {
            Character[] array = element.toArray(new Character[0]);
            for (int i = 0; i < array.length; i++) {
                builder.append(array[i]);
            }
        }

        backTrack("", 0, len, res, builder.toString());


    }

    private void backTrack(String path, int index, int len, ArrayList<String> res, String str) {
        if (path.length() == len) {
            res.add(new String(path));
            return;
        }

        for (int i = index; i < str.length(); i += 1) {
            backTrack(path + str.charAt(i), i + 2, len, res, str);
        }


    }

    public List<String> letterCombinations2(String digits) {
        ArrayList<String> res = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }

        //建立键盘
        String[] keyBoard = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        backTrack2("", 0, digits, res, keyBoard);

        return res;
    }

    /**
     * @Author 李红磊
     * @Date 2021/11/3 15:32
     * @param: cur 路径变量
     * @param: i
     * @param: str 目标字符
     * @param: res 用于返回
     * @param: keyBoard
     **/
    private void backTrack2(String cur, int i, String str, ArrayList<String> res, String[] keyBoard) {
        if (cur.length() == str.length()) {
            res.add(cur);
            return;
        }

        //获取数字对应的键盘
        String key = keyBoard[str.charAt(i) - 48];

        //对键盘进行遍历
        for (int j = 0; j < key.length(); j++) {
            backTrack2(cur + key.charAt(j), i + 1, str, res, keyBoard);

        }
    }


    //22.括号生成
    public List<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<>();
        if (n == 1) {
            res.add("()");
            return res;
        }

        generate("", n, n, res);

        return res;
    }

    /**
     * @Date 2021/11/3 16:34
     * @param: cur 路径变量，记录当下拼凑的括号
     * @param: leftNum 左括号数量
     * @param: rightNum 右括号数量
     * @param: res 用于返回
     **/
    private void generate(String cur, int leftNum, int rightNum, ArrayList<String> res) {

        if (leftNum == 0 && rightNum == 0) {
            res.add(cur);
            return;
        }
        if (leftNum > rightNum || leftNum < 0 || rightNum < 0) {
            return;
        }
        generate(cur + "(", leftNum - 1, rightNum, res);
        generate(cur + ")", leftNum, rightNum - 1, res);


    }

    //79.单词搜索
    public boolean exist(char[][] board, String word) {
        char firstLetter = word.charAt(0);
        int rows = board.length, columns = board[0].length;


        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == firstLetter) {
                    if (isExist(i, j, board, word, 1)) return true;
                }

            }
        }


        return false;
    }

    private boolean isExist(int x, int y, char[][] board, String word, int num) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return false;
        }
        if (num == word.length()) {
            return true;
        }

        if (board[x][y] == word.charAt(num)) {
            return true;
        }

        if (isExist(x - 1, y, board, word, num)) isExist(x - 1, y, board, word, num + 1);
        if (isExist(x + 1, y, board, word, num)) isExist(x + 1, y, board, word, num + 1);
        if (isExist(x, y - 1, board, word, num)) isExist(x, y - 1, board, word, num + 1);
        if (isExist(x, y + 1, board, word, num)) isExist(x, y + 1, board, word, num + 1);


        return false;

    }

    public boolean exist2(char[][] board, String word) {
        char firstLetter = word.charAt(0);
        int rows = board.length, columns = board[0].length;
        boolean[][] visit = new boolean[rows][columns];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == firstLetter) {
                    if (dfs(i, j, 0, board, word, visit)) return true;
                }
            }
        }


        return false;
    }

    private boolean dfs(int x, int y, int index, char[][] board, String word, boolean[][] visit) {
        if (index == word.length() - 1) {
            return board[x][y] == word.charAt(word.length() - 1);
        }

        if (board[x][y] != word.charAt(index)) {
            return false;
        }

        visit[x][y] = true;
        int[] directions = {-1, 0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int newX = x + directions[i];
            int newY = y + directions[i + 1];
            if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length && !visit[newX][newY]) {
                if (dfs(newX, newY, index + 1, board, word, visit)) {
                    return true;
                }


            }

        }
        visit[x][y] = false;

        return false;

    }


    //面试题10.03 搜索旋转数组
    public int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        if (arr[left] < arr[right]) {//说明没有旋转
            //直接进行二分

            while (left <= right) {
                int mid = left + right >> 1;
                if (arr[mid] == target) {
                    return mid;
                } else if (target > arr[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

            }

            return -1;
        }

        //程序走到这，说明数组发生了旋转，那么我们就寻找旋转点
        while (arr[left] > arr[right]) {
            left++;
        }
        //现在left就指向旋转点
        //开始对这两部分进行二分查找
        int twoLeft = left;
        while (twoLeft <= right) {
            while (twoLeft <= right) {
                int mid = twoLeft + right >> 1;
                if (arr[mid] == target) {
                    return mid;
                } else if (target > arr[mid]) {
                    twoLeft = mid + 1;
                } else {
                    right = mid;
                }

            }

        }

        int oneLeft = 0;
        int oneRight = left - 1;
        while (oneLeft < oneRight) {
            int mid = oneLeft + oneRight >> 1;
            if (arr[mid] == target) {
                return mid;
            } else if (target > arr[mid]) {
                oneLeft = mid + 1;
            } else {
                oneRight = mid - 1;
            }
        }

        return -1;
    }

    public int search2(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            if (arr[left] != target) {
                left++;
            } else {
                return left;
            }
        }


        return -1;
    }

    //面试题10.05 洗漱数组搜索
    public int findString(String[] words, String s) {
        if (words.length == 1 && words[0].equals(s)) {
            return 0;
        }
        int left = 0, right = words.length - 1;

        while (left <= right) {
            //将让left和right指向字母
            while (left < right && words[left].equals("")) left++;
            while (left < right && words[right].equals("")) right--;

            int mid = left + right >> 1;
            int temp = mid;
            while (temp < right && words[temp].equals("")) temp++;
            if (words[temp].compareTo(s) > 0) {
                right = mid - 1;
            } else if (words[temp].compareTo(s) < 0) {
                left = mid + 1;
            } else {
                return temp;
            }

        }


        return -1;
    }


    public static void main(String[] args) {
        t20211103 t20211103 = new t20211103();
        System.out.println(t20211103.findString(new String[]{"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""}, "ball"));

    }

}
